Search for: All records

Abstract Theq-colour Ramsey number of ak-uniform hypergraphHis the minimum integerNsuch that anyq-colouring of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofH. The study of these numbers is one of the central topics in Combinatorics. In 1973, Erdős and Graham asked to maximise the Ramsey number of a graph as a function of the number of its edges. Motivated by this problem, we study the analogous question for hypergaphs. For fixed$$k \ge 3$$and$$q \ge 2$$we prove that the largest possibleq-colour Ramsey number of ak-uniform hypergraph withmedges is at most$$\mathrm{tw}_k(O(\sqrt{m})),$$where tw denotes the tower function. We also present a construction showing that this bound is tight for$$q \ge 4$$. This resolves a problem by Conlon, Fox and Sudakov. They previously proved the upper bound for$$k \geq 4$$and the lower bound for$$k=3$$. Although in the graph case the tightness follows simply by considering a clique of appropriate size, for higher uniformities the construction is rather involved and is obtained by using paths in expander graphs. 

Abstract Given a $$k$$-uniform hypergraph $$H$$ on $$n$$ vertices, an even cover in $$H$$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalization of cycles in graphs and are equivalent to linearly dependent subsets of a system of linear equations modulo $$2$$. As a result, they arise naturally in the context of well-studied questions in coding theory and refuting unsatisfiable $$k$$-SAT formulas. Analogous to the irregular Moore bound of Alon, Hoory, and Linial [3], Feige conjectured [8] an extremal trade-off between the number of hyperedges and the length of the smallest even cover in a $$k$$-uniform hypergraph. This conjecture was recently settled up to a multiplicative logarithmic factor in the number of hyperedges [12, 13]. These works introduce the new technique that relates hypergraph even covers to cycles in the associated Kikuchi graphs. Their analysis of these Kikuchi graphs, especially for odd $$k$$, is rather involved and relies on matrix concentration inequalities. In this work, we give a simple and purely combinatorial argument that recovers the best-known bound for Feige’s conjecture for even $$k$$. We also introduce a novel variant of a Kikuchi graph which together with this argument improves the logarithmic factor in the best-known bounds for odd $$k$$. As an application of our ideas, we also give a purely combinatorial proof of the improved lower bounds [4] on 3-query binary linear locally decodable codes. 

Abstract Theq-color Ramsey number of ak-uniform hypergraphG,  denotedr(G; q), is the minimum integerNsuch that any coloring of the edges of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofG. The study of these numbers is one of the most central topics in combinatorics. One natural question, which for triangles goes back to the work of Schur in 1916, is to determine the behavior ofr(G; q) for fixedGandqtending to infinity. In this paper, we study this problem for 3-uniform hypergraphs and determine the tower height ofr(G; q) as a function ofq. More precisely, given a hypergraphG, we determine whenr(G; q) behaves polynomially, exponentially or double exponentially inq. This answers a question of Axenovich, Gyárfás, Liu and Mubayi. 

We study the following question raised by Erdős and Hajnal in the early 90’s. Over all n n -vertex graphs G G what is the smallest possible value of m m for which any m m vertices of G G contain both a clique and an independent set of size log ⁡ n \log n ? We construct examples showing that m m is at most 2 2 ( log ⁡ log ⁡ n ) 1 / 2 + o ( 1 ) 2^{2^{(\log \log n)^{1/2+o(1)}}} obtaining a twofold sub-polynomial improvement over the upper bound of about n \sqrt {n} coming from the natural guess, the random graph. Our (probabilistic) construction gives rise to new examples of Ramsey graphs, which while having no very large homogenous subsets contain both cliques and independent sets of size log ⁡ n \log n in any small subset of vertices. This is very far from being true in random graphs. Our proofs are based on an interplay between taking lexicographic products and using randomness.